package com.practice.suffixtree;

import java.util.HashMap;
import java.util.Set;

public class LongestCommonSubstring {
	public String find(String a, String b) {
		TrieNode root = new TrieNode();
		buildSuffix(root, a, 1);
		buildSuffix(root, b, 2);
		return findLongestCommon(root);
	}
	
	private String findLongestCommon(TrieNode node) {
		int maxLen = 0;
		String maxStr = "";
		for (char c : node.keys()) {
			TrieNode child = node.get(c);
			String sub = findLongestCommon(child);
			if (child.isCommon(3)) sub = c + sub;
			if (sub.length() > maxLen) {
				maxLen = sub.length();
				maxStr = sub;
			}
		}
		return maxStr;
	}
	
	private void buildSuffix(TrieNode root, String str, int bit) {
		char[] c = str.toCharArray();
		for (int i=c.length-1; i>=0; i--) {
			TrieNode parent = root;
			for (int j=0; j<c.length-i; j++) {
				parent = parent.addChild(c[i+j], bit);
			}
		}
	}
	
	private class TrieNode {
		private HashMap<Character, TrieNode> 	map;
		private int								bit;
		
		public TrieNode() {
			map = new HashMap<Character, TrieNode>();
		}
		
		public TrieNode addChild(char c, int bit) {
			if (!map.containsKey(c)) {
				map.put(c, new TrieNode());
			}
			this.bit |= bit;
			return map.get(c);
		}
		
		public boolean isCommon(int bit) {
			return this.bit == bit;
		}
		
		public Set<Character> keys() {
			return map.keySet();
		}
		
		public TrieNode get(char c) {
			return map.get(c);
		}
	}
}
